In many data processing systems, there is provided between the working store of the central processing unit and the main store, a high speed buffer storage unit which is commonly called a "cache". This unit enables a relatively fast access to a subset of data and instructions which were previously transferred from main storage to the cache, and thus improves the speed of operation of the data processing system. The transfer of operands or instructions between main store and cache is usually effected in fixed-length units which are called blocks or "lines" of information. The selection of lines for transfer to the cache, and also their location in cache (except for a possible pre-assignment of classes to cache sub-areas) depend on the respective program, the operands used, and the events that happen during program execution.
To enable retrieval of information from the cache, a table of tags or line addresses is maintained in a "directory" which is an image of the cache. Each line residing in cache has its tag or address stored in the respective position in the directory. Once the cache is filled-up, new information can only be entered if an old block or line of information is deleted or overwritten. Certain procedures are necessary to select lines as candidates for replacement, and to update the directory after a change of the cache contents.
A number of systems are known in the art which use cache or high speed buffer stores and provide a mechanism for replacement selection and directory updating.
U.S. Pat. No. 4,322,795 to R. E. Lange et al. discloses a cache memory arrangement using a least-recently-used scheme for selecting a cache location in which to store data fetched from main memory upon a cache miss. A directory which stores tag address bits of data available in cache is provided in duplicate for each cache to improve operation in a multiprocessor system having multiple caches. Both directories have the same contents, i.e. the tags for data (operands, instructions) presently in cache. One directory is used as usual for retrieval of requested data. The other is used for comparing the address of data stored in the cache of its associated CPU A to the addresses of data changed in main memory by another processor, CPU B. The data stored in the cache of CPU A must be invalidated if they were changed in main store by another CPU, and the duplicate directory is a tool for this process.
U.S. Pat. No. 4,332,010 to B. U. Messina et al. describes a cache buffer system using a directory which is subdivided into classes. Due to some overlap in translatable and non-translatable portions in the addresses used, and depending on where the data is stored actually in cache, there may be either a miss, or a principal hit in one specific class, or a synonym hit in other classes when an access is tried. The system disclosed solves the problem of possible time loss when only a synonym hit will occur, by addressing and searching all classes of the directory simultaneously so that if no principal bit occurs, the synonym hit is available immediately.
U.S. Pat. No. 4,168,541 to C. W. DeKarske discloses a replacement system for a set associative cache buffer, i.e. a cache which is subdivided into sets each associated with a class of data having some address bits in common. The system uses age bits to determine the least recently used (LRU) block in a set. The age bits are updated each time a block is referenced. A directory (tag buffer) is provided for storing tags representing a portion of the address bits of data words currently in the cache memory. The patent describes details of updating the directory and the age bits.
U.S. Pat. No. 4,189,770 to P. M. Gannon et al. describes a cache bypass control for operand fetches. In the disclosed system, if a cache miss occurs and a line must be fetched from main storage, that portion (operands) of the fetched line, which was requested and is immediately needed is directly transferred to the I-Unit via a cache bypass. This avoids the time delay caused by waiting until the complete line had been transferred to the cache, thus allowing faster operation and improving efficiency of the system. U.S. Pat. No. 4,195,343 to T. F. Joyce discloses a replacement procedure for a cache store which is organized in levels. Selection of locations in which replacement occurs if new data are to be placed into the cache is done by a round-robin mechanism.
None of the prior art references discloses the anticipatory fetching, or prefetching into the cache buffer store of information that was not yet requested, to thus reduce the probability of a cache miss if that information is actually requested subsequently.